from typing import *


class Solution:
    def validSequence(self, word1: str, word2: str) -> List[int]:
        m, n = len(word1), len(word2)
        if n == 1:
            return [0]
        dp, i, j = [None] * (n + 1), n - 1, m - 1
        # "bbeigiibhjafjig", "iihhj"
        while i >= 0 and j >= 0:
            w2 = word2[i]
            while j >= 0 and word1[j] != w2:
                j -= 1
            if j != -1:
                dp[i] = j
                j -= 1
            i -= 1
        j = 0
        ans = []
        for i, v in enumerate(word2):
            if j >= m:
                break
            if word1[j] == v:
                ans.append(j)
                j += 1
            elif i == n - 1:
                ans.append(j)
                break
            elif dp[i + 1] is None or dp[i + 1] <= j:
                while j < m and word1[j] != v:
                    j += 1
                if j < m:
                    ans.append(j)
                j += 1
            else:
                ans.append(j)
                k = j + 1
                i += 1
                while k < m and i < n:
                    while k < m and word1[k] != word2[i]:
                        k += 1
                    ans.append(k)
                    k += 1
                    i += 1
                return ans
        return [] if len(ans) < n else ans


so = Solution()
print(so.validSequence("bbeigiibhjafjig", "iihhj"))
print(so.validSequence("aaaaaa", "aaabc"))
print(so.validSequence("ccbccccbcc", "b"))
print(so.validSequence("bacdc", "abc"))
print(so.validSequence("vbcca", "abc"))
#
#
